#include<bits/stdc++.h>
using namespace std;
const int N = 60;
const int MOD = 998244353;
int S[N],sp;
int tong[N];
int cc[N];
bool vis[N];
int jc[N];
int jc_1[N];
int gcdl[N][N];
vector<int> bian[N];
int qpow(int x,int p){
	int res = 1;
	while(p){
		if(p & 1){
			res = 1ll*x*res%MOD;
		}
		x = 1ll*x*x%MOD;
		p >>= 1;
	}
	return res;
}
int tc;
int pc;
void dfs1(int x){
	vis[x] = 1;
	tc += cc[x];
	pc++;
	for(int v: bian[x]){
		if(!vis[v]){
			dfs1(v);
		}
	}
}
int ans = 0;
int ans1 = 0;
int ans2 = 0;
int n;
void dfs(int val){
	if(!val){
		int k = 0;
		int k1 = 0;
		int bk = 0;
		for(int i = 1;i<=sp;i++){
			cc[i] = 0;
			vis[i] = 0;
			bian[i].clear();
		}
		for(int i = 1;i<=sp;i++){
			if(S[i] % 2 == 0){
				bk += S[i]/2 - 1;
				cc[i]++;
				k1++;
			}else{
				bk += S[i]/2;
			}
			k += (S[i] - 1)/2;
		}
		int ecnt = 0;
		for(int i = 1;i<=sp;i++){
			for(int j = i + 1;j <= sp;j++){
				int g = gcdl[S[i]][S[j]];
				if(S[i]/g % 2 == 1 && S[j]/g % 2 == 1){
					bian[i].push_back(j);
					bian[j].push_back(i);
					ecnt += g;
				}else if(S[j]/g % 2 == 1){
					cc[i] += g;
				}else if(S[i]/g % 2 == 1){
					cc[j] += g;
				}else{
					ecnt += g;
				}
				k += g;
			}
		}
		int res = qpow(2,bk);
		for(int i = 1;i<=sp;i++){
			if(!vis[i]){
				tc = 0;
				pc = 0;
				dfs1(i);
				tc = max(tc - 1,0);
				res = 1ll*res*qpow(2,tc)%MOD;
				ecnt -= pc - 1;
			}
		}
		res = 1ll*res*qpow(2,ecnt)%MOD;
		int w = 1;
		for(int i = 1;i<=sp;i++){
			w = 1ll*w*jc_1[S[i]]%MOD*jc[S[i] - 1]%MOD;
		}
		for(int i = 1;i<=n;i++){
			w = 1ll*w*jc_1[tong[i]]%MOD;
		}
		ans = (ans + 1ll*w*res%MOD)%MOD;
		ans1 = (ans1 + 1ll*w*qpow(4,k)%MOD*qpow(2,k1)%MOD)%MOD;
		ans2 = (ans2 + 1ll*w*qpow(3,k)%MOD)%MOD;
		return;
	}
	for(int i = 1;i<=min(val,S[sp]);i++){
		S[++sp] = i;
		tong[i]++;
		dfs(val - i);
		tong[i]--;
		sp--;
	}
}
int main(){
	cin>>n;
	S[0] = n + 1;
	jc[0] = jc_1[0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			gcdl[i][j] = __gcd(i,j);
		}
	}
	for(int i = 1;i<=n;i++){
		jc[i] = 1ll*jc[i - 1]*i%MOD;
		jc_1[i] = qpow(jc[i],MOD - 2);
	}
	dfs(n);
	//cout<<ans1<<'\n';
	cout<<ans<<'\n';
	//cout<<ans2<<'\n';
}